Engineers, computer programmers, and other designers use simulations to assist in the development of new or improved products, methods and systems. Often, these simulations are mathematical models of the system being designed. For example, mathematical models have been developed of the turbine blades for jet engine aircraft, energy states of molecular electronic components, industrial DC motors, and many other devices and systems. These mathematical models do not physically exist. They are equations and formulas used by engineers, programmers and other designers to predict and simulate the performance and design of the device or system being modeled. The mathematical models may exist only in the notebooks and computers of the designers.
The mathematical models enable a designer to design on paper (or in a computer) a new product or system, without going through the time and expense of building a prototype for each design variation. Using the mathematical models, many different simulations of a new product, method or system may be analyzed. The simulations may be varied by changing the starting or input variables for the mathematical model. The best solution(s) to a mathematical model can be selected for further evaluation. For example, the best solution developed by a mathematical model may be built as a physical prototype to test whether the solution developed by the model is actually the best design.
For example, a mathematical model of an I-beam, such as used in building construction, may have fixed variables, such as its length, and several variable parameters, such as the fixed and variable loading capacity, beam weight, beam height, flange width, fillet curvature, and beam shape. Some of the parameters may be selected by the designer at the start of the design, and other parameters may be determined by the mathematical model in simulating the I-beam design. An I-beam designer can vary the values of certain input parameters, such as desired load capacity and weight, to determine how the selected input parameter values affect the I-beam design. By varying the values of the input parameters, several alternative I-beam designs will be generated by the mathematical model. Some of these generated I-beam designs will be better than others. Varying the input parameter values and order of selection of input parameters, allows the designer to evaluate many potential I-beam designs and select the optimal design for further evaluation and actual use.
It is tedious and time consuming to manually vary the input parameters of a mathematical model. There may be thousands, millions or more possible variations of input parameters to a given mathematical model. It is not practical for a human designer to manually vary the different parameters of many modern-day mathematical models. Computer executed optimization programs have been developed to vary the input parameters of computer models. By having a computer vary the input parameters, the number of simulated designs that can be generated using a mathematical models is dramatically greater than the number of designs that can be generated manually. Current optimization programs are given an initial a set of starting conditions and constraints that are used to generate a first solution to a mathematical model or simulation. Subsequent, solutions of the model or simulation are generated as the optimization program perturbs, i.e., varies, the input parameters within set constraints. By generating many, e.g., hundreds, thousands, millions, of solutions to the mathematical model or simulation, the optimization program searches for an optimal (or at least a better) solution to the model, given a set of constraints and goals the problem and solution must satisfy.
Most prior optimization techniques are limited to a specific application. These prior techniques are not generic search techniques that can be applied to a variety of different models or simulations. In the past, for example, an optimization program that was generated for a particular model such as related to a physics problem, was not applicable to optimizing a model of a chemical system. Prior optimization techniques have been created to utilize certain specific knowledge or experience of a particular system or design. There has been a need for a generic optimization system that can be tailored to a particular model or problem, by importing into the optimization system the knowledge of persons expert in the field related to the model or problem.
In addition, most prior expert optimization systems require a full knowledge base before starting an optimization search. These prior systems require an expert to establish a complete set of rules to govern a design or solution. In the real world, designers do not have a complete knowledge on which to establish an expert system or the time with which to perfect such a system. There is a long felt need for a heuristic optimization system which operates with less than a complete base of expert knowledge, and makes use of that knowledge that is available to search for a solution to a model or simulation.
In the field of optimization methods, most methods are numerically based techniques, such as mathematical mapping algorithms and mathematical extrapolations between known solution points or beyond known points. Numerical techniques often evaluate a model to predict how the model responds to changes in input parameters. The evaluations usually involve mathematical extrapolations and estimations, based on assumptions that the model will react to gradual changes in input parameters by gradually changing the output characteristics of the solution. If the solutions to a model do not change gradually with gradual changes in inputs, then numerical methods have difficulty in extrapolating between solutions of the models. For example, if certain solutions to a model are dramatically different, such as if the solution rapidly spikes to a higher value, then numerical techniques have difficulty in predicting such drastic changes by extrapolating from other solutions.
A numerical optimization method generally treats the variable parameters of a design as independent numbers that can be systematically changed. Numerical methods tend not to account for whether a particular parameter is significant to the desired characteristic of the solution. Accordingly, numerical methods may waste much time in changing variables that do not effect the solution, or that yield impractical solutions.
Another class of optimization search technique, these techniques are called "exploratory", which include genetic algorithms and simulated annealing. These two examples of exploratory techniques essentially randomly pick inputs within the specified domain and rank the resulting solutions. Those inputs with a good solution are weighted and futures guessed are made in the vicinity of the better solutions, with the idea that good solutions form neighborhoods in and around local optima. These exploratory techniques tend to require relatively large numbers of computations because the techniques are not limited to searching only the local neighborhood of the best design point.
Symbolic optimization methods rely on techniques, such as expert and rule based systems, and heuristic searches, that do not rely on mathematical formula. Heuristic techniques that have been used in symbolic optimization methods have been implemented as processes employing trial-and-error and informed guesses to search for optimal solutions to symbolic systems. Previous symbolic systems were front ends systems to numeric optimizers. In a sense, the symbolic systems steered the numerical optimization programs to solutions. The symbolic systems did not themselves perform any search, but rather directed a numerical search technique. Also, most rule systems, a type of symbolic system, tend to favor single selection of rules, even when multiple rules may apply. For example, some rule systems used a weighted random selection of rules, but only selected a single rule. DHS is not a symbolic system, but does incorporate certain ideas from rule based systems such as building and defining rules like objects, such as dependencies. DHS works with the entire set of applicable dependencies and uses each applicable dependency during each cycle.
Standard numerical optimization techniques have a variety of drawbacks that limit their usefulness. For example, present-day numerical techniques do not incorporate real-world design knowledge to provide efficient searches. Real-world design knowledge is the experience and judgment that a seasoned human designer will have developed. For example, a human designer will know based on his own experience that certain solutions are impractical. A numerical optimization technique, lacking the benefit of a designer's experience, will generate impractical solutions in a blind search for optimal solutions. Another problem is that current numerical methods do not efficiently handle the important and frequent problem of dynamic limits that result where an input constraint depends on the values of other input variables. In general, numerical methods require that additional output constraints be added for each input constraint. The drawback of this approach is that many fruitless design evaluations are made with inputs that violate bounds because they are cast as output constraints and must be evaluated before the violation is detected. It would be advantageous for numerical optimization methods to incorporate some of the expert knowledge known to experienced designers, and better handle dynamic limits that depend on one or more variable input parameters.
Furthermore, numerical optimization methods are inefficient in their treatment of design variables. In particular, numerical methods, especially many domain independent search techniques, consider all design variable parameters as equal in rank and treat the parameters uniformly. In realistic models, design parameters are not equal in rank, as some input parameters affect particular features or performance criteria of a design to a much greater extend than do other input parameters. By ranking all input variables equally, numerical techniques make it difficult to determine how each parameter affects the model and the search for an optimal solution. By treating all variable input parameters equally, numerical methods tend to waste resources in changing parameters that only marginally affect the desired features of a design. It would be desirable if numerical optimization methods would identify the parameters which most affect a desired design feature and recognize how those parameters affected the desired feature.
Another problem with numerical optimization methods is that they are susceptible to local optimas that may cause a numerical optimization method to terminate on a less than fully optimal solution. Numerical methods are usually designed to gradually move towards a maximum value, and away from decreasing values. Accordingly, a local optima, which is a local maximum value surrounded by lower values, will cause a numerical method to stop because the method is incapable of moving off the local optima to find a greater optimal value.
To understand the problem of become stuck on a local optima, it is convenient to consider by way of analogy a hill-climbing robot instructed to find tall hills by climbing only up hill. The robot is instructed never to travel downhill. When the robot reaches the top of any hill, even a small hill, the robot will stop because any further movement from the hilltop is downhill. If the hilltop that the robot is stuck on is a minor foot-hill in the shadow of a mountain range, the robot will never find the higher mountains.
Like the hill-climbing robot, numerical optimization techniques move only towards more optimal solutions and never move in a direction away from a more optimal solutions. Numerical optimization techniques can become stuck on solutions that are local optimas. Once stuck on a local optima, numerical techniques do not know how to move off that optima to find better solutions. Human designers do not generally become stuck on local optimas. A knowledgeable designer will recognize a local optima solution and move the design process onto better solutions. Designers know how and when to move in a direction away from a local optima, even if that direction initially leads the designer to less optimal solutions. It would be desirable if a numerical optimization method would also be able to move off a local optima and on to better solutions.
Another short-coming with most numerical techniques is that they assume that variable design parameters are continuous, when some real-life parameters vary only in discrete steps. The gradients used by numerical search techniques do not accommodate well a parameter that varies incrementally only in steps. In addition, numerical optimization techniques using finite difference techniques (used to approximate gradients) require that the finite differences be calculated for each parameter before starting any optimization search. Since the calculation of finite differences can greatly influence the direction of an optimization search, the use of finite differences with discrete and integer parameters will poorly approximate the gradient and result in inefficient searches.
Numerical, symbolic and exploratory optimization techniques have been combined into a type of software tool box, in which these different techniques may be applied on a case-by-case basis. The Engineous Software Company of Morrisville, N.C., has been selling its iSIGHT.TM. software product for optimizing designs. The iSIGHT.TM. provides a software suite of various optimization software techniques, including numerical techniques, genetic algorithms, and simulated annealing search tools. These techniques do not incorporate knowledge about the simulated problem or design solutions of the type that a human designer would have. To provide this domain-specific knowledge to guide the search, the iSIGHT.TM. software also includes symbolic knowledge-based search tools, such as expert rule techniques, that can be applied in conjunction with the each optimization technique in the tool box.
However, prior to the present invention, the search tools available with iSIGHT.TM. did not include techniques that provided the human designer with near complete control over a search for an optimal solution to a model. Prior to the present invention, designers were not able to direct an optimization search by identifying the most influential input parameters with respect to specific output parameters, establishing the mode of sequencing goals and parameters to be used during a search, specifying the direction that a parameter should be varied to achieve a desired result on an input parameter, and other controls that the human design can use to direct an optimization search. The present invention is a software search technique that provides a human design with tremendous control and flexibility over an optimization search.